package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/10 14:15
 */
public class Nineteen {
    public static void main(String[] args){
        Nineteen nineteen = new Nineteen();

        System.out.println(nineteen.jumpGame2(new int[]{2, 1, 5, 1, 1, 2, 1, 1}));
        //System.out.println(seventeen.findOriginal(753));
    }

    public int jumpGame(int[] arr){
        if (arr.length == 1) {
            return 0;
        }
        if (arr.length == 2) {
            return 1;
        }
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[arr.length - 1] = 0;
        for (int i = arr.length - 2; i >= 0; i--) {
            for (int j = 1; j <= arr[i]; j++) {
                if (i + j < arr.length) {
                    dp[i] = Math.min(dp[i], dp[j + i] + 1);
                }

            }
        }
        return dp[0];

    }

    //O(n)
    public int jumpGame2(int[] arr){
        int step = 0;//走几步
        int max = 0;//走几步能够达到最远的地方
        int next = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (i > max) {
                step++;
                max = next;
                next = 0;
            }
            next = Math.max(next, i + arr[i]);

            if (next >= arr.length - 1) {//提前结束
                return step + 1;
            }
        }
        return -1;
    }

}
